package com.xinwei.linearExercise;

import java.util.Arrays;

/**
 * 动态数组
 */
public class ArrayList<E> extends AbstractList<E> {
    //所有元素,当数组是泛型时，数组实际上存储的是对象的地址，而并非对象本身
    private E[] elements;

    private static final int DEFAULT_CAPATICY = 10;

    public ArrayList(int capaticy) {
        capaticy = (capaticy < DEFAULT_CAPATICY) ? DEFAULT_CAPATICY : capaticy;
        elements = (E[]) new Object[capaticy];
    }

    public ArrayList() {
        this(DEFAULT_CAPATICY);
    }

    public E get(int index) {  // 复杂度O(1)
        rangeCheck(index);
        return elements[index];
    }

    public E set(int index, E element) {  // 复杂度O(1)
        if (index > 0 && index < size) return elements[index];
        E old = elements[index];
        elements[index] = element;
        return old;
    }

    public int indexof(E element) {
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if (elements[i] == null) {
                    return i;
                }
            }
        }else {
            for (int i = 0; i < elements.length; i++) {
                // 这里改成equals，默认是比较内存地址，对象可对equals方法进行重写，使指定属性相等时判断为对象相等
                if (element.equals(elements[i])) return i;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    public void clear() {
        //这样在使用者看来就已经是清空了数组，若直接把elements设为null，使用者再次调用add方法需要重新创建数组，消耗时间（性能）
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    public E remove(int index) {
        /**
         *  最好：O(1)
         *  最坏：O(n）
         *  平均：O(n)
         */
        rangeCheck(index);
        E old = get(index);
        for (int i = index + 1; i < size - 1; i++) {
            elements[index] = elements[index + 1];
        }
        elements[--size] = null;
        return old;
    }

    public void add(int index, E element) {
        /**
         *  最好：O(1)
         *  最坏：O(n）
         *  平均：O(n)
         */
        rangeCheckForAdd(index);
        ensureCapacity(size + 1);
        for (int i = size; i > index; i--) {
            elements[i] = elements[i - 1];
        }
        size++;
        elements[index] = element;
    }

    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("size = ").append(size).append(", [");
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(", ");
            }
            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }

    /**
     * 封装
     */

    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity < capacity) {
            // 这里oldCapacity >> 1相当于oldCapacity/2
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            E[] newElements = (E[]) new Object[newCapacity];
            for (int i = 0; i < size; i++) {
                newElements[i] = elements[i];
            }
            elements = newElements;
        }
    }
}
